//  二叉搜索树
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node(int val) {
        this.val = val;
    }
}
public class BinarySearchTree {
    public Node root = null;

//    查找
    public Node search(int key) {
        Node cur = root;
        while (cur != null) {
            if (key > cur.val) {
                cur = cur.right;
            }else if (key == cur.val) {
                return cur;
            }else {//key < cur.val
                cur = cur.left;
            }
        }
        return null;
    }
//    插入
    public boolean insert(int val) {
        if (root == null) {
            root = new Node(val);
            return true;
        }


        Node cur = root;
        Node parent = null;

        while (cur != null) {
            if (val > cur.val) {
                parent = cur;
                cur = cur.right;
            }else if (val < cur.val) {
                parent = cur;
                cur = cur.left;
            }else{//val == cur.val
                return false;//不能有相同的数据
            }
        }
        if (val > parent.val) {
            parent.right = new Node(val);
        }
        if (val < parent.val) {
            parent.left = new Node(val);
        }
        return true;
    }





//      删除 复杂

//        1. cur.left == null
//              1. cur 是 root，则 root = cur.right
//              2. cur 不是 root，cur 是 parent.left，则 parent.left = cur.right
//              3. cur 不是 root，cur 是 parent.right，则 parent.right = cur.right
//        2. cur.right == null
//              1. cur 是 root，则 root = cur.left
//              2. cur 不是 root，cur 是 parent.left，则 parent.left = cur.left
//              3. cur 不是 root，cur 是 parent.right，则 parent.right = cur.left
//        3. cur.left != null && cur.right != null
//              1.在cur的左树中找最大值   最大值覆盖cur 再删除最大值
//              2.在cur的右树中找最小值   最小值覆盖cur 再删除最小值
    public void remove(int key) {
        Node cur = root;
        Node parent = null;
        while (cur != null) {
            if (key == cur.val) {
//                这里进行删除
                removeNode(cur,parent);
            }else if (key < cur.val) {
                parent = cur;
                cur = cur.left;
            }else {//key > cur.val
                parent = cur;
                cur = cur.right;
            }
        }
    }

    /**
     * 删除节点
     * @param cur   需要删除的节点
     * @param parent    需要删除的节点的父节点
     */
    public void removeNode(Node cur,Node parent) {
//        1.要删除节点的左边为空
        if (cur.left == null) {
            if (cur == root) {
                root = cur.right;
            }else if (cur == parent.left) {
                parent.left = cur.right;
            }else {//cur == parent.right
                parent.right = cur.right;
            }
        }

//        2.要删除节点的右边为空
        if (cur.right == null) {
            if (cur == root) {
                root = cur.left;
            }else if (cur == parent.left) {
                parent.left = cur.left;
            }else {//cur == parent.right
                parent.right = cur.left;
            }
        }

//        3.要删除节点的左右都不为空
        if (cur.left != null && cur.right != null) {
//            右边找最小值
            Node targetParent = null;
            Node target = cur.right;
            while (target.left != null) {
                targetParent = target;
                target = target.left;
            }
            cur.val = target.val;

//            这里还有两种情况
            if (targetParent.left == target) {
                targetParent.left = target.right;
            }else {//
                targetParent.right = target.right;
            }
        }
    }


    public void inOrder(Node root) {
        if(root == null) return;
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }


    public static void main(String[] args) {
        int[] array = {10,8,23,5,2,67,21};
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        for (int i = 0; i < array.length; i++) {
            binarySearchTree.insert(array[i]);
        }
        binarySearchTree.inOrder(binarySearchTree.root);
//        2 5 8 10 21 23 67
        System.out.println("插入重复的数据");
        System.out.println(binarySearchTree.insert(2));//false
        System.out.println("删除数据");
        binarySearchTree.remove(10);
        binarySearchTree.inOrder(binarySearchTree.root);
//        2 5 8 21 23 67
    }
}
